【题解】 不同子串个数 后缀数组.SA luoguP2408 | Qiuly's blog!

【题解】 不同子串个数 后缀数组.SA luoguP2408

Posted on | In | Comments:

后缀数组。

假设我们现在已经求出了 $height$ 数组，我们发现，对两个后缀，其重复了的字串的个数就是 $height$ 数组所记录的数。我们举个例子：

后缀$sa[i-1]$: $aaabbdbs$
后缀$sa[i]$ : $aabbdbs$

会发现，最前面的”$aa$”是两个串都有的，”$aa$”中包含的”$a$”也是两个串都有的，这样子就有两个重复的了，可以发现这个重复个数正好是 $height[i]$ 的值。

但是后面还是有重复的啊？没关系，因为我们有所有的后缀，所以整个串中所有的重复的串都会被统计进来。所以这下子我们可以很容易的求出整个串中重复的串的个数了，就是 $\sum_{i=1}^{n}height[i]$ 。

子串的个数显然是 $\frac{n(n+1)}{2}$ ，这两项相减就是我们需要的答案了，记得开 $longlong$ 。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+2;
const int inf=1e9+9;

namespace Suffix_array {
    char s[N];
    int sa[N],x[N],y[N],hep[N],height[N],n,m;
    void Sort() {
        for(int i=0;i<=m;++i) hep[i]=0;
        for(int i=1;i<=n;++i) ++hep[x[i]];
        for(int i=1;i<=m;++i) hep[i]+=hep[i-1];
        for(int i=n;i>=1;--i) sa[hep[x[y[i]]]--]=y[i];
    }
    void Pre_sa() {
        for(int i=1;i<=n;++i) x[i]=s[i],y[i]=i;
        m=129;Sort();
        for(int w=1,p=0;m=p,p<n;w<<=1) {
            p=0;
            for(int i=1;i<=w;++i) y[++p]=n-w+i;
            for(int i=1;i<=n;++i) if(sa[i]>w) y[++p]=sa[i]-w;
            Sort(),swap(x,y),x[sa[1]]=p=1;
            for(int i=2;i<=n;++i)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;
        }return;
    }
    ll Pre_height() {
        for(int i=1;i<=n;++i) x[sa[i]]=i;
        int k=0,res=0;
        for(int i=1;i<=n;++i) {
            k-=k>0;
            int j=sa[x[i]-1];
            while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) ++k;
            height[x[i]]=k,res+=k;
        }return res;//直接返回height数组的和
    }
}using namespace Suffix_array;

int main() {
    scanf("%d\n",&n);
    scanf("%s",s+1);
    Pre_sa();
    ll ans=1ll*n*(n+1)/2;
    ans-=Pre_height();
    printf("%lld\n",ans);
    return 0;
}

本文标题:【题解】 不同子串个数 后缀数组.SA luoguP2408

文章作者:Qiuly

发布时间:2019年04月10日 - 00:00

最后更新:2019年04月10日 - 15:28

原始链接:http://qiulyblog.github.io/2019/04/10/[题解]luoguP2408/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。